Did you know you can estimate the value of π (pi) using probability and number theory?

This challenge explores a surprising mathematical relationship:
The probability that two randomly chosen integers are coprime, P(\text{coprime}) is equal to \frac{6}{\pi^2}

Coprime numbers?

Two numbers are coprime if their only common factor is 1.

Using this idea, you can estimate π by randomly generating pairs of integers and checking how often they are coprime.
​
If:
P(\text{coprime}) = \frac{6}{\pi^2} ​
Then we can rearrange to estimate π:
\pi \approx \sqrt{\frac{6}{P(\text{coprime})}} ​

So the aim of this challenge will be to write a program to:

• Generate many random pairs of integers
• Count how many of these pairs are coprime
• Use the ratio to estimate π

Not that to work out if two numbers are coprime, we will need to create a function to calculate their Greatest Common Denominator.

Step 1: Generating N pairs of random integers

For this step we will use the random library to generate random integer values (between 1 and 10,000), and a for loop, to generate N pairs.

import random, math

N = 1000
for i in range(0,N):
   number1 = random.randint(1,10000)
   number2 = random.randint(1,10000)

Step 2: Finding out if our pair of numbers are coprime

To check if two numbers are coprime, we first need to calculate their Greatest Common Denominator. We can do so using the following function, based on Euclid’s Division Algorithm:

def gcd(a, b):
    # Repeat until b becomes 0
    while b != 0:
        remainder = a % b   # Find the remainder when a is divided by b
        a = b               # Move b into a
        b = remainder       # Move remainder into b

    # When b is 0, a contains the GCD
    return a

We can use this function in our previous for loop to count how many pairs of numbers are coprime:

import random, math

N = 1000
coprime_count = 0

for i in range(0,N):
   number1 = random.randint(1,10000)
   number2 = random.randint(1,10000)
   if gcd(number1, number2) == 1:
      coprime_count = coprime_count + 1

Step 3: Outputting the ratio of coprime pairs:

We can now calculate and display the ratio of coprime pairs (Probability that two randomly generated numbers are coprime):

probability = coprime_count / N

Estimating Pi

We can now estimate Pi using the following formula:
\pi \approx \sqrt{\frac{6}{P(\text{coprime})}}

pi_estimate = math.sqrt(6 / probability)

And finally we can display our estimate on screen as well as calculate the percentage of accuracy of our estimate:

print("Number of pairs", N)
print("Number of coprime", coprime_count)
print("Estimated value of Pi:", pi_estimate)
print("Actual value of Pi:", math.pi)
print("Percentage of accuracy:", 100 - 100 * abs(math.pi - pi_estimate)/math.pi)

Python Code

Your turn! You can now complete the code below:

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

The Goldbach Conjecture is an unproven mathematical rule, proposed by Christian Goldbach in 1742, stating that every even integer greater than 2 is the sum of two prime numbers. Despite verification by computers up to 4 x 10¹⁸, no formal proof exists, making it one of the oldest unsolved problems in number theory!

Every even number greater than 2 can be expressed as the sum of two prime numbers.

Let’s look at some examples:

• 10 = 3 + 7
• 28 = 5 + 23
• 50 = 3 + 47

Our challenge is to write a Python program that tests this conjecture for any even number provided by the end-user of this program. Our program will need to:

Ask the user to enter an even number greater than 2
Find two prime numbers that add up to this number
Display the result

Example Output

Enter an even number: 28
28 = 5 + 23

Prime Numbers?

A prime number is a whole number greater than 1 that cannot be exactly divided by any whole number other than itself and 1.

The first 20 prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71.

To help test the Goldbach Conjecture, we will use a function isPrime() that takes a whole positive number as a parameter and returns whether or not this number is a prime number. Here is the code for this function:

def isPrime(n):
   if n < 2:
      return False
   for i in range(2, int(n**0.5) + 1):
      if n % i == 0:
         return False
   return True

You can test this function using the following code:

number = int(input("Enter a whole number"))
if isPrime(number):
   print("This number is a prime number!")
else:
   print("This number is a not a prime number!")

Testing the Goldbach Conjecture

We are now going to implement an algorithm to test the Goldbach Conjecture for any given number. We will base our Python code on the following flowchart:

Python Code

Use the following IDE to complete the code for testing the Goldbach conjecture based on the above flowchart:

Extension Task

Tweak your code to use an iterative approach to check all even numbers from 4 up to 1000 and display their prime pairs.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

The Basel Problem

In the 17th century, mathematicians became fascinated by an infinite series known as the Basel Problem.
The question was simple to state but extremely difficult to solve:

This can also be written using sigma notation:
\sum_{n=1}^{\infty}(1 / n²)

Many famous mathematicians attempted to solve it, including members of the Bernoulli family who lived in the Swiss city of Basel (hence the name of the problem). However, no one could determine its exact value.

That changed in 1734, when the brilliant mathematician Leonhard Euler discovered something remarkable.

Euler’s Remarkable Discovery

Euler proved that the infinite series actually equals:

This result surprised mathematicians because it revealed a deep connection between:

• Number theory (the sum of reciprocals of squares)
• Geometry through the constant π

Rearranging Euler’s formula allows us to express π in terms of the series:

This means we can estimate π by computing a partial sum of the series.
The more terms we include, the closer we get to the true value of π.

Approximating π Numerically

Since we cannot compute an infinite number of terms, we approximate the series using the first N values:

As N increases, the approximation becomes more accurate.
This is a perfect opportunity to use Python and an iterative algorithm to calculate an approximate value of Pi using a large number of iterations (N).

Python Challenge

Your challenge is to write a Python program that estimates the value of π using Euler’s solution to the Basel Problem.

Your program should:

Ask the user how many terms of the series should be calculated.
Use a loop to calculate the sum of 1 / n².
Use Euler’s formula to estimate π.
Display the estimated value of π.
Display the percentage of accuracy of your estimate compared to Python’s math.pi.

Example Output:

How many terms should be used? 10000

Estimated value of Pi: 3.14149
Actual value of Pi: 3.141592653589793
Difference: 0.00010

You can now complete the code using the following Python IDE:

Improving the Accuracy

The accuracy depends on the number of terms used.

The true value of π is approximately 3.14159265359, so the estimate improves steadily as N increases.
However, this method converges relatively slowly compared to modern algorithms such as the Gregory-Leibniz series or the Nilakantha series.

Find out more Python challenges based on estimating π using your Python skills:

• Calculating Pi using the Gregory-Leibniz series or the Nilakantha series
• Calculating Pi using the Monte Carlo Method
• Calculating Pi using Buffon’s Needle

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Passwords are the first line of defence protecting our online accounts. But how secure is your password really?

In this Python challenge we will create a program that estimates how long it would take for a hacker to guess a password using a brute-force attack.

A brute-force attack works by trying every possible password combination until the correct one is found.

Check our online password checker tool to estimate how secure your password is, and to estimate how long it would take for for a hacker to crack your password using a brute force attack.

Step 1 – Understanding Password Strength

The difficulty of cracking a password depends on two main factors.

1. Password Length

Longer passwords take much longer to guess.

2. Character Variety

Passwords become stronger if they include:

• Lowercase letters (a–z)
• Uppercase letters (A–Z)
• Numbers (0–9)
• Symbols (!@#$%^&*)

The more character types used, the larger the number of possible combinations.

Step 2 – Calculating Possible Passwords

If a password uses N possible characters and has a length of L, the total number of combinations is:

Example:

For a password that only contains 3 lowercase letters of the alphabet:

26³ = 17,576 combinations

Step 3 – Estimating Guessing Speed

Modern brute-force tools can test billions of guesses per second.

For this project we will assume:

1,000,000,000 guesses per second

The time to crack the password is therefore:

Step 4 – Python Program

To create our own “password Security Estimator” we will start by asking the user to enter a password.

password = input("Enter a password: ")

We will then work out the number of possible characters used in this password by evaluating if this password contains lowercase characters, uppercase characters, number digits and punctuation signs.

N = 0

#Let's find out if this password contains lowercase characters
for character in password:
   if character in "abcdefghijklmnopqrstuvwxyz":
      N = N + 26
      break

Now we can repeat this approach to see if the password includes uppercase characters, number digits or punctuation signs:

#Let's find out if this password contains uppercase characters
for character in password:
   if character in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
      N = N + 26
      break

#Let's find out if this password contains number digits
for character in password:
   if character in "0123456789":
      N = N + 10
      break

#Let's find out if this password contains punctuation signs
for character in password:
   if character in "!""#$%&'()*+,-./:;<=>?@[\]^_`{|}~":
      N = N + 32
      break

We can now word out the length of the password:

L = len(password)

We can apply the formula to calculate the total number of possible combinations using the ** operator (to the power of).

combinations = N ** L

The next step is to estimate, how long, in seconds, it would take to a brute force through all these combinations based on an estimate of 1 billion guesses per seconds.

guessesPerSecond = 1000000000
seconds = combinations / guessesPerSecond

Finally we will output the results using the most appropriate unit of time (milliseconds, seconds, minutes, hours, days, months or years). To do so we will create a function to format/convert the number of seconds to the most appropriate unit of time.

def formatTime(seconds):

    if seconds < 0.001:
        return "a few milliseconds"

    if seconds < 60:
        return str(int(seconds)) + " seconds"

    minutes = seconds / 60
    if minutes < 60:
        return str(int(minutes)) + " minutes"

    hours = minutes / 60
    if hours < 24:
        return str(int(hours)) + " hours"

    days = hours / 24
    if days < 365:
        return str(int(days)) + " days"

    months = days / 30
    if months<12:
        return str(int(months)) + " months"

    years = days / 365
    return str(int(years)) + " years"

print("Estimated cracking time: " + formatTime(seconds))

Example Output

Example 1

Enter a password: abc
Estimated cracking time: a few milliseconds

Example 2

Enter a password: password
Estimated cracking time: 0.02 seconds

Example 3

Enter a password: pa$$word!
Estimated cracking time: 85 days

Your Turn

Type the code provided below in the following online IDE and estimate the time it would take to crack the following passwords:

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area